package com.sheng.leetcode.year2023.month08.day21;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/8/21
 * <p>
 * 2337. 移动片段得到字符串<p>
 * <p>
 * 给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：<p>
 * 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时<p>
 * 才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。<p>
 * 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。<p>
 * 如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：start = "_L__R__R_", target = "L______RR"<p>
 * 输出：true<p>
 * 解释：可以从字符串 start 获得 target ，需要进行下面的移动：<p>
 * - 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。<p>
 * - 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。<p>
 * - 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。<p>
 * 可以从字符串 start 得到 target ，所以返回 true 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：start = "R_L_", target = "__LR"<p>
 * 输出：false<p>
 * 解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。<p>
 * 但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。<p>
 * <p>
 * 示例 3：<p>
 * 输入：start = "_R", target = "R_"<p>
 * 输出：false<p>
 * 解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。<p>
 * <p>
 * 提示：<p>
 * n == start.length == target.length<p>
 * 1 <= n <= 10^5<p>
 * start 和 target 由字符 'L'、'R' 和 '_' 组成<p>
 */
public class LeetCode2337 {

    @Test
    public void test01() {
//        String start = "_L__R__R_", target = "L______RR";
//        String start = "R_L_", target = "__LR";
//        String start = "_R", target = "R_";
        String start = "_L", target = "LL";
        System.out.println(new Solution().canChange(start, target));
    }
}

class Solution {
    public boolean canChange(String start, String target) {
        // 满足 start 字符串中的 L 和 R 和 target 在顺序上必须保持一致
        int n = start.length();
        // index1 代表字符串 start 中的坐标，index2 代表字符串 target 中的坐标
        int index1 = 0, index2 = 0;
        while (index1 < n && index2 < n) {
            // 跳过空格
            while (index1 < n - 1 && start.charAt(index1) == '_') {
                index1++;
            }
            while (index2 < n - 1 && target.charAt(index2) == '_') {
                index2++;
            }
            if (start.charAt(index1) != target.charAt(index2)) {
                // 如果排除掉空格后两个字符串的字符不相同，那么顺序不同，无法一致
                return false;
            } else {
                if (start.charAt(index1) == 'L' && index1 < index2) {
                    // 如果两个字符都是 L，那么 index1 的坐标必须在 index2 后面，才能在之后向左移动
                    return false;
                } else if (start.charAt(index1) == 'R' && index1 > index2) {
                    // 如果两个字符都是 R，那么 index1 的坐标必须在 index2 前面，才能在之后向右移动
                    return false;
                }
            }
            index1++;
            index2++;
        }
        // 如果没有到末尾，那么之后的所有字符都必须是空格
        while (index1 < n) {
            if (start.charAt(index1++) != '_') {
                return false;
            }
        }
        while (index2 < n) {
            if (target.charAt(index2++) != '_') {
                return false;
            }
        }
        return true;
    }
}
